package com.zjsru.oneDay202210;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

/**
 * @Author: CookLee
 * @Date: 2022/10/8
 *  优势洗牌
 * 给定两个大小相等的数组nums1和nums2，nums1相对于 nums2 的优势可以用满足nums1[i] > nums2[i]的索引 i的数目来描述。
 *
 * 输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
 * 输出：[2,11,7,15]
 */
public class AdvantageCount {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        int n = nums1.length;
        TreeSet<Integer> set = new TreeSet<>();
        Map<Integer,Integer> map = new HashMap<>();
        for (int num: nums1) {
            map.put(num,map.getOrDefault(num , 0) + 1);
            //方便后续计数，将计数为1的数字填入TreeSet
            if(map.get(num) == 1){
                set.add(num);
            }
        }
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            //ceiling用来返回在此设定为大于或等于给定的元素的最小元素
            Integer cur = set.ceiling(nums2[i] + 1);
            if(cur == null){
                //获取上一个数字
                cur = set.ceiling(-1);
            }
            //将符合要求的添入ans数组中
            ans[i] = cur;
            //如果有符合要求的数字就计数-1
            map.put(cur,map.get(cur) - 1);
            //若计数为 0，则将该数值从候选集合中移除。
            if(map.get(cur) == 0){
                set.remove(cur);
            }
        }
        return ans;
    }
    
    public static void main(String[] args) {
        AdvantageCount advantageCount = new AdvantageCount();
        int[] nums1 = new int[]{2,7,11,11,15};
        int[] nums2 = new int[]{1,10,7,4,11};
        System.out.println(Arrays.toString(advantageCount.advantageCount(nums1, nums2)));
    }
}
